/*
 * pairingheap.h
 *
 * 一种配对堆实现
 *
 * Portions Copyright (c) 2012-2022, PostgreSQL Global Development Group
 *
 * src/include/lib/pairingheap.h
 */

#ifndef PAIRINGHEAP_H
#define PAIRINGHEAP_H

#include "lib/stringinfo.h"

/* 如果需要 pairingheap_dump() 调试函数，请启用此选项 */
/* #define PAIRINGHEAP_DEBUG */

/*
 * 这表示存储在堆中的一个元素。将其嵌入到一个包含实际数据的
 * 更大结构中。
 *
 * 一个节点可以有多个子节点，形成一个双向链表。
 * first_child 指向节点的第一个子节点，后续的子节点
 * 可以通过跟随 next_sibling 指针找到。最后一个子节点的
 * next_sibling == NULL。prev_or_parent 指针指向节点的
 * 前一个兄弟节点，或者如果节点是其父节点的第一个子节点，则指向
 * 父节点。
 */
typedef struct pairingheap_node
{
	struct pairingheap_node *first_child;
	struct pairingheap_node *next_sibling;
	struct pairingheap_node *prev_or_parent;
} pairingheap_node;

/*
 * 返回 'ptr' 所指向的 pairingheap_node 的 'type' 所包含的结构。
 *
 * 这用于将 pairingheap_node * 转换回其包含的结构。
 */
#define pairingheap_container(type, membername, ptr) \
	(AssertVariableIsOfTypeMacro(ptr, pairingheap_node *), \
	 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node),  \
	 ((type *) ((char *) (ptr) - offsetof(type, membername))))

/*
 * 类似于 pairingheap_container，但在指针为 'const ptr' 时使用
 */
#define pairingheap_const_container(type, membername, ptr) \
	(AssertVariableIsOfTypeMacro(ptr, const pairingheap_node *), \
	 AssertVariableIsOfTypeMacro(((type *) NULL)->membername, pairingheap_node),  \
	 ((const type *) ((const char *) (ptr) - offsetof(type, membername))))

/*
 * 对于最大堆，比较器必须返回 <0 当且仅当 a < b，返回 0 当且仅当 a == b，
 * 和 >0 当且仅当 a > b。对于最小堆，条件是反转的。
 */
typedef int (*pairingheap_comparator) (const pairingheap_node *a,
									   const pairingheap_node *b,
									   void *arg);

/*
 * 配对堆。
 *
 * 您可以使用 pairingheap_allocate() 创建一个新的 palloc'd 堆，或将
 * 其嵌入到更大的结构中，直接设置 ph_compare 和 ph_arg 并初始化
 * ph_root 为 NULL。
 */
typedef struct pairingheap
{
	pairingheap_comparator ph_compare;	/* 比较函数 */
	void	   *ph_arg;			/* 传递给 ph_compare 的不透明参数 */
	pairingheap_node *ph_root;	/* 堆的当前根节点 */
} pairingheap;

extern pairingheap *pairingheap_allocate(pairingheap_comparator compare,
										 void *arg);
extern void pairingheap_free(pairingheap *heap);
extern void pairingheap_add(pairingheap *heap, pairingheap_node *node);
extern pairingheap_node *pairingheap_first(pairingheap *heap);
extern pairingheap_node *pairingheap_remove_first(pairingheap *heap);
extern void pairingheap_remove(pairingheap *heap, pairingheap_node *node);

#ifdef PAIRINGHEAP_DEBUG
extern char *pairingheap_dump(pairingheap *heap,
							  void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
							  void *opaque);
#endif

/* 重置堆为空。 */
#define pairingheap_reset(h)			((h)->ph_root = NULL)

/* 堆是空的吗？ */
#define pairingheap_is_empty(h)			((h)->ph_root == NULL)

/* 堆中是否恰好有一个节点？ */
#define pairingheap_is_singular(h) \
	((h)->ph_root && (h)->ph_root->first_child == NULL)

#endif							/* PAIRINGHEAP_H */
